Network probing with low overhead has prompted a flurry of research activity in recent past. A research project called the ID maps project produced the latency maps of the Internet from which latencies of any arbitrary path can be obtained. However, because only relatively few paths are actually monitored, it is possible to make errors in estimating the latencies of any arbitrary path. An overlay network setting finds the minimal set of paths to monitor, so that the behavior of all paths can be inferred. One existing solution is to compute the minimum cost set of multicast trees that can cover links of particular interest in the network.
Recently, algorithms have been provided for selecting probe stations such that all links are covered and the minimal set of probe paths that must be transmitted by each station are computed, such that the latency of every link can be measured. However, the probe paths are computed via Internet protocol (IP) routes available from the probing stations. The problem of probe-path design has been considered where local flexibility was assumed. The probe-paths can be selected as either the current IP route or one of the current IP routes of the immediate neighbors. The efficient probe node (called beacon) placement strategy provides the minimum number of probe nodes required to deterministically monitor all network links even in the presence of dynamism in IP routes.
All of these existing works on probe-paths and probe-node location have focused on IP routes as potential probe-paths. There is a need to focus on explicitly routed probe packets. One work studied the problem of measuring path latencies through explicitly routed packet probes, while minimizing the overhead imposed by the probe traffic. However, the probe packets are required to originate from a central point in the network. There is a need for link-cover algorithms to focus on the design of probe paths. This differs from existing work, probe paths can be chosen (source-routed) that originate and terminate from any given set of terminal nodes in the network. This new problem setting raises the following questions: (1) how to define a probe, (2) how to find a minimum cost set of probes to cover a given set of edges, and (3) what is the tradeoff between the number of probes and the cost of probes?